package sort

import (
	"container/list"
	"math/rand"
	"time"
	"traning/algorithm/utility"
)

func LessThanLast(arr []int){
	lessArea := -1
	index := 0
	Len := len(arr)
	for index < Len {
		if arr[index] <= arr[Len-1] {
			utility.Swap(arr, lessArea+1, index)
			lessArea++
			index++
		} else {
			index++
		}
	}
}

func QuickSort(arr []int){
	quickProcess(arr, 0, len(arr)-1)
}

type Job struct {
	left int
	right int
}

func QuickSort2(arr []int){
	job := Job{left:0, right:len(arr)-1}
	stack := list.New()
	stack.PushBack(job)
	for stack.Len() > 0 {
		job := stack.Remove(stack.Back()).(Job)
		mL, mR := partition(arr, job.left, job.right)
		if mL-1 > job.left {
			stack.PushBack(Job{left:job.left, right: mL-1})
		}
		if mR+1 < job.right {
			stack.PushBack(Job{left:mR+1, right: job.right})
		}
	}
}

func quickProcess(arr []int, l, r int){
	if l >= r {return}
	mL, mR := partition(arr, l, r)
	quickProcess(arr, l, mL-1)
	quickProcess(arr, mR+1, r)
}

// 荷兰国旗问题
func partition(arr []int, l, r int) (int, int) {
	if len(arr) < 2{return 0 , 0}
	lessArea := l-1
	biggerArea := r
	index := l
	rand.Seed(time.Now().UnixNano())
	ranIndex := l + rand.Intn(r-l+1)
	utility.Swap(arr, ranIndex, r)
	for index < biggerArea {
		if arr[index] < arr[r] {
			utility.Swap(arr, index, lessArea+1)
			index++
			lessArea++
		} else if arr[index] > arr[r] {
			utility.Swap(arr, index, biggerArea-1)
			biggerArea--
		} else {
			index++
		}
	}
	utility.Swap(arr, biggerArea, r)
	// 返回等于区左右边界
	return lessArea+1, biggerArea
}

